BZOJ3110 K大数查询 <树套树>

Problem

K大数查询

Description

有个位置，个操作。操作有两种，每次操作如果是的形式表示在第个位置到第个位置，每个位置加入一个数；如果是形式，表示询问从第个位置到第个位置，第大的数是多少。

Input

第一行，
接下来行，每行形如或

Output

输出每个询问的结果

Sample Input

Sample Output

1
2
3

1
2
1

Hint

样例说明
第一个操作后位置的数只有，位置的数也只有。第二个操作后位置的数有、，位置的数也有、。第三次询问位置到位置第大的数是。第四次询问位置到位置第大的数是。第五次询问位置到位置第大的数是。
数据规模

操作中
操作中

标签：值域线段树套区间线段树

Solution

这道题乍一看时主席树，但实际上是树套树。
外层值域线段树，内层区间线段树，外层只提供内层的根的位置，真正参与计算的是内层。

Code

#include <iostream>
#include <cstdio>
#define MAX_N 50000
using namespace std;
typedef long long ll;
int n, m, cnt;
int root[(MAX_N<<2)+500], ls[MAX_N*16*16+500], rs[MAX_N*16*16+500];
ll tr[MAX_N*16*16+500], tag[MAX_N*16*16+500];
inline void updata(int v, int s, int t) {tr[v] = tr[ls[v]]+tr[rs[v]]+tag[v]*(ll)(t-s+1);}
//内层修改
void modify(int &v, int s, int t, int l, int r) {
    if (!v)	v = ++cnt;
    if (s >= l && t <= r) {tr[v] += (ll)(t-s+1), tag[v]++; return;}
    int mid = s+t>>1;
    if (l <= mid)	modify(ls[v], s, mid, l, r);
    if (r >= mid+1)	modify(rs[v], mid+1, t, l, r);
    updata(v, s, t);
}
//外层修改
void insert(int v, int s, int t, int l, int r, int x) {
    modify(root[v], 1, n, l, r);
    if (s == t)	return;
    int mid = s+t>>1;
    if (x <= mid)	insert(v<<1, s, mid, l, r, x);
    if (x >= mid+1)	insert(v<<1|1, mid+1, t, l, r, x);
}
//内层查询
ll calc(int v, int s, int t, int l, int r) {
    if (!v)	return 0;	
    if (s >= l && t <= r)	return tr[v];
    int mid = s+t>>1;
    ll ret = tag[v]*(ll)(min(t, r)-max(s, l)+1);
    if (l <= mid)	ret += calc(ls[v], s, mid, l, r);
    if (r >= mid+1)	ret += calc(rs[v], mid+1, t, l, r);
    return ret;
}
//外层查询
ll query(int v, int s, int t, int l, int r, int k) {
    if (s == t)	return s;
    int mid = s+t>>1;
    ll tmp = calc(root[v<<1|1], 1, n, l, r);
    if (k >= tmp+1)	return query(v<<1, s, mid, l, r, k-tmp);
    if (k <= tmp)	return query(v<<1|1, mid+1, t, l, r, k);
}
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int opt, a, b, c;
        scanf("%d%d%d%d", &opt, &a, &b, &c);
        if (opt == 1)	insert(1, 1, n, a, b, c);
        if (opt == 2)	printf("%lld\n", query(1, 1, n, a, b, c));
    }
    return 0;
}